package com.leetcode.algorithm.topic;

import java.util.Stack;

/**
 * 栈相关算法题解
 * (done)20. 有效的括号
 * (TODO)739. 每日温度
 * (done)150. 逆波兰表达式求值
 * @author: jie.deng
 * @time: 2019年4月9日 下午11:52:50
 */
public class StackSolution {
    
    /**
     * 20. 有效的括号 
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
     * 
     * 有效字符串需满足： 
     * 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 
     * 注意空字符串可被认为是有效字符串。
     * 
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if (s == null || "".equals(s)) {
            return true;
        }
        Stack<Character> stack = new Stack<Character>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch = s.charAt(i);
            switch (ch) {
            case '(':
            case '{':
            case '[':
                stack.push(ch);
                break;
            case ')':
                if (!stack.isEmpty() && stack.pop() == '(') {
                    break;
                } else {
                    return false;
                }
            case '}':
                if (!stack.isEmpty() && stack.pop() == '{') {
                    break;
                } else {
                    return false;
                }
            case ']':
                if (!stack.isEmpty() && stack.pop() == '[') {
                    break;
                } else {
                    return false;
                }
            default:
                return false;
            }
        }
        return stack.isEmpty();
    }

    /**
     * 739. 每日温度
     * 
     * 根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。
     * 
     * 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
     * 
     * 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。
     * @param T
     * @return
     */
    public int[] dailyTemperatures(int[] T) {
        return T;
    }
    
    /**
     * 150. 逆波兰表达式求值
     * 
     * 根据逆波兰表示法，求表达式的值。
     * 
     * 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     * 
     * 说明：
     * 
     * 整数除法只保留整数部分。
     * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
     * 示例 1：
     * 
     * 输入: ["2", "1", "+", "3", "*"]
     * 输出: 9
     * 解释: ((2 + 1) * 3) = 9
     * 示例 2：
     * 
     * 输入: ["4", "13", "5", "/", "+"]
     * 输出: 6
     * 解释: (4 + (13 / 5)) = 6
     * 示例 3：
     * 
     * 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
     * 输出: 22
     * 解释: 
     *   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
     * = ((10 * (6 / (12 * -11))) + 17) + 5
     * = ((10 * (6 / -132)) + 17) + 5
     * = ((10 * 0) + 17) + 5
     * = (0 + 17) + 5
     * = 17 + 5
     * = 22
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        // 1)如果是数字，先将其转换为整数再入栈
        // 2)如果是运算符，将两个操作数出栈，计算结果再入栈
        // 3)重复1）和2）直到后缀表达式结束，最终栈内的元素即为计算的结果。
        int ret = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (String str : tokens) {
            if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
                if (stack.size() >= 2) {
                    int i1 = stack.pop();
                    int i2 = stack.pop();
                    if ("+".equals(str)) {
                        ret = i2 + i1;
                    } else if ("-".equals(str)) {
                        ret = i2 - i1;
                    } else if ("*".equals(str)) {
                        ret = i2 * i1;
                    } else if ("/".equals(str)) {
                        ret = i2 / i1;
                    }
                    stack.push(ret);
                }
            } else {
                stack.push(Integer.parseInt(str));
            }
        }
        return stack.pop();
    }
}